机器学习

大纲

机器学习

一般流程

原始数据：表格、图片、视频、文本、语音、……

特征工程：

• 提取：选取、构造对目标任务有用的潜在特征
• 处理：无序的离散类别特征 → 数值特征，缺失处理，标准化
• 变换：对特征进行挑选或映射得到对目标任务更有效的特征

模型学习：最核心的部分，学习一个用来预测的映射

监督学习

所有样本都有类别标记

任务类型：

• 二分类：$y \in \{ 1, -1 \}$或者$y \in \{ 0,1 \}$
• 多分类：$y \in [C] = \{ 1, 2, \ldots, C \}$
• 回归：$y \in \Rbb$或连续集合
• 结构预测：$y$可以是向量、序列、语法树、……

二分类示例

多分类示例

混淆矩阵

回归

线性回归：用最小二乘求解超定方程组 (方程个数比未知数多)

无监督学习

所有样本都没有类别标记

任务类型：

• 聚类 (clustering)：依相似度将数据分成$K$个簇 (cluster)
• 降维/嵌入：为样本学习新的特征
• 密度估计：估计样本空间的概率密度$\Pr(\xv)$，寻找数据的生成机制

聚类

• 原始数据由 6 个簇组成
• K 均值算法指定聚成 4 个簇，每种颜色对应一个簇，菱形为簇中心

密度估计

• 直方图是最简单的密度估计方法 (数数)，对区间的选择极其敏感
• 核密度估计：$\rho(\zv) = \sum_{i \in [m]} \kappa ((\zv-\xv_i)/\sigma)$

密度估计

• 核密度估计：$\rho(\zv) = \sum_{i \in [m]} \kappa ((\zv-\xv_i)/\sigma)$

大纲

机器学习方法分类

米哈尔斯基 等《机器学习：一种人工智能途径》
Machine Learning: An Artificial Intelligence Approach

• 从样本中学习
• 在问题求解和规划中学习
• 通过观察和发现学习
• 从指令中学习

费根鲍姆 等《人工智能手册》
The Handbook of Artificial Intelligence

• 机械学习，死记硬背式学习，信息存储检索
• 示教学习，类似于“从指令中学习”
• 类比学习，类似于“通过观察和发现学习”
• 归纳学习，类似于“从样本中学习”，目前研究最多、应用最广

机器学习流派

多明戈斯 Pedro Domingos
《终极算法》The Master Algorithm

• 符号学派：规则学习，决策树
• 连接学派：感知机，神经网络
• 进化学派
• 统计学派：朴素贝叶斯，贝叶斯网
• 类推学派：k-近邻，支持向量机

灵魂问题：哪个算法更好？

没有免费的午餐定理 (No Free Lunch Theorem, NFL 定理)

• 脱离具体的问题空谈什么算法好没有意义
• 学习算法自身的归纳偏好应与问题相匹配

约还是不约？

女人心海底针 让机器学习读心术来拯救你

符号学派

用“若……且……则……”形式的合取规则尽可能地覆盖正样本

$(\text{方式} = \text{逛街}) \wedge (\text{温度} = \text{暖和}) \rightarrow (\text{约会} = \text{是})$

• 可解释强，用户可以秒懂，学习中易于引入人类知识
• 将规则集合组织成树的形式即为决策树

连接学派

用带阈值的线性函数拟合数据

$\sgn(w_0 + w_1 \cdot \text{次序} + \cdots + w_5 \cdot \text{电视}) \rightarrow \{\text{是}, \text{否}\}$

• 知识是分布式存储的，由权重系数$w_0, w_1, \ldots, w_5$表示
• 将上述函数广泛并行串联就是神经网络

统计学派

利用贝叶斯公式求后验概率

$\Pr (\text{约会}|\text{次序},\ldots,\text{电视}) = \frac{\Pr (\text{次序},\ldots,\text{电视}|\text{约会}) \Pr (\text{约会}) \qquad \quad}{\Pr (\text{次序},\ldots,\text{电视}) \qquad}$

• 先验$\Pr (\text{约会})$反映了在没有任何信息的情况下对答应约会的信念
• 数据通过似然$\Pr (\text{次序},\ldots,\text{电视}|\text{约会})$调整我们对答应约会的信念

类推学派

引入相似度函数$s(\cdot, \cdot)$和样本权重$\alpha$

$\sgn(\alpha_1 \cdot s(\xv_1, \xv_5) \cdot y_1 + \cdots + \alpha_4 \cdot s(\xv_4, \xv_5) \cdot y_4) \rightarrow \{\text{是}, \text{否}\}$

• k-近邻：$s$为欧氏距离，距离最小的$k$个样本权重为$1$，其余为$0$
• 支持向量机：$s$为核函数，权重为对偶问题拉格朗日乘子变量

模型评估 回归

给定模型$f$、数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$

均方误差 (mean squared error, MSE)

$$ \begin{align*} E_D (f) = \frac{1}{m} \sum_{i \in [m]} (f(\xv_i) - y_i)^2 \end{align*} $$

>>> from sklearn.metrics import mean_squared_error

>>> y_true = [3, -0.5, 2, 7]
>>> y_pred = [2.5, 0.0, 2, 8]

>>> mean_squared_error(y_true, y_pred) # MSE
0.375

>>> mean_squared_error(y_true, y_pred, squared=False) # RMSE
0.6123724356957945

模型评估 分类

给定模型$f$、数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$

错误率 (error rate)、精度 (accuracy)

$$ \begin{align*} E_D (f) = \frac{1}{m} \sum_{i \in [m]} \Ibb (f(\xv_i) \ne y_i), ~ \acc(f;D) = 1 - E_D (f) \end{align*} $$

>>> from sklearn.metrics import accuracy_score

>>> y_true = [0, 1, 2, 3]
>>> y_pred = [0, 2, 1, 3]

>>> accuracy_score(y_true, y_pred) # 百分比
0.5

>>> accuracy_score(y_true, y_pred, normalize=False) # 正确分类的个数
2

查准率 查全率 F1

二分类结果的混淆矩阵 (confusion matrix)

查准率 (precision)：预测的约会中有多少比例真的约会了

查全率 (recall)：所有的约会中有多少比例被预测出来了

$$ \begin{align*} & \mathrm{precision} = \frac{\TP}{\TP + \FP}, \quad \mathrm{recall} = \frac{\TP}{\TP + \FN} \\[4pt] & \mathrm{F1} = \frac{2 \cdot \mathrm{Precision} \cdot \mathrm{Recall}}{\mathrm{Precision} + \mathrm{Recall}} = \frac{2 \cdot \TP}{\text{样本总数} + \TP - \TN \quad} \end{align*} $$

查准率 查全率 F1

>>> from sklearn.metrics import confusion_matrix
>>> from sklearn.metrics import precision_score, recall_score, f1_score

>>> y_true = [1, 1, 0, 0, 1, 0, 1, 0]
>>> y_pred = [0, 1, 0, 1, 1, 1, 1, 0]

>>> cm = confusion_matrix(y_true, y_pred, labels=[1,0])
>>> cm
array([[3, 1],
       [2, 2]])

>>> tp, fn, fp, tn = cm.ravel()
>>> tp, fn, fp, tn
(3, 1, 2, 2)

>>> precision_score(y_true, y_pred)
0.6

>>> recall_score(y_true, y_pred)
0.75

>>> f1_score(y_true, y_pred)
0.6666666666666665

模型选择 回归

选择宗旨：在未知数据上表现好，即泛化 (generalization) 好

特征空间$\Xcal \subset \Rbb^d$，标记空间$\Ycal \subset \Rbb$，$\Xcal \times \Ycal$上的未知分布$\Dcal$

给定模型$f$，训练数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$，其中$(\xv_i, y_i) \overset{\mathrm{iid}}{\sim} \Dcal$

经验 (empirical) 均方误差 (训练数据集上的均方误差)

$$ \begin{align*} E_D (f) = \frac{1}{m} \sum_{i \in [m]} (f(\xv_i) - y_i)^2 \end{align*} $$

泛化均方误差，可通过测试 (test) 数据集来近似估计

$$ \begin{align*} E_{\Dcal} (f) = \Ebb_{(\xv,y) \sim \Dcal} [(f(\xv) - y)^2] = \Ebb_{D \sim \Dcal^m} [E_D (f)] \end{align*} $$

模型选择 分类

选择宗旨：在未知数据上表现好，即泛化 (generalization) 好

特征空间$\Xcal \subset \Rbb^d$，标记空间$\Ycal$，$\Xcal \times \Ycal$上的未知分布$\Dcal$

给定模型$f$，训练数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$，其中$(\xv_i, y_i) \overset{\mathrm{iid}}{\sim} \Dcal$

经验 (empirical) 错误率 (训练数据集上的错误率)

$$ \begin{align*} E_D (f) = \frac{1}{m} \sum_{i \in [m]} \Ibb (f(\xv_i) \ne y_i) \end{align*} $$

泛化错误率，可通过测试数据集来近似估计

$$ \begin{align*} E_{\Dcal} (f) = \Ebb_{(\xv,y) \sim \Dcal} [\Ibb(f(\xv) \ne y)] = \Ebb_{D \sim \Dcal^m} [E_D (f)] \end{align*} $$

欠拟合 过拟合

训练集：余弦函数中随机采样的$30$个点加上$0.1$的随机噪声

学习算法：$n$阶多项式回归，$n=1$即为线性回归

$$ \begin{align*} \min_{w_j} ~ g (w_j) = \frac{1}{2} \sum_{i \in [30]} \left( \sum_{j=0}^n w_j x_i^j - y_i \right)^2 \end{align*} $$

其中$w_0, w_1, \ldots, w_n$为待求参数

目标函数$g$关于$w_j$的偏导数为

$$ \begin{align*} \frac{\partial g}{\partial w_j} = \sum_{i \in [30]} \left( \sum_{j=0}^n w_j x_i^j - y_i \right) x_i^j \end{align*} $$

欠拟合 过拟合

左图：1 阶多项式欠拟合 (underfitting)，经验均方误差很大

中图：4 阶多项式拟合地最好，最贴近真实模型

右图：30 阶多项式过拟合 (overfitting)，经验均方误差为零

模型选择 验证

事先选定合适的模型 (归纳偏倚) 很重要！

从训练集中随机选择一部分样本作为验证集 (validation set)

• 在剩余的训练集上训练一个学习模型
• 在验证集上计算模型的误差

据此比较多个候选模型的性能

交叉验证 (cross validation)：将训练集平均分为$n$份，每轮

• 在其中$n-1$份上训练一个学习模型
• 在剩余的$1$份上计算模型的误差

迭代$n$轮取平均，据此比较多个候选模型的性能

偏差方差分解

以回归问题为例，对任意样本$(\xv,y) \sim \Dcal$，均方误差可分解为

$$ \begin{align*} (f (\xv) & - y)^2 = (f (\xv) - \Ebb [y|\xv] + \Ebb [y|\xv] - y)^2 \\ & = (f (\xv) - \Ebb [y|\xv])^2 + (\Ebb [y|\xv] - y)^2 + 2 (f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) \end{align*} $$

其中条件期望$\Ebb [y|\xv]$与$y$无关，对交叉项有

$$ \begin{align*} \Ebb_{(\xv,y)} & [(f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) ] \\ & = \iint (f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) \Pr(\xv, y) \diff \xv \diff y \\ & = \int (f (\xv) - \Ebb [y|\xv]) \left( \int (\Ebb [y|\xv] - y) \Pr(\xv, y) \diff y \right) \diff \xv \\ & = \int (f (\xv) - \Ebb [y|\xv]) \underbrace{ ( \Ebb [y|\xv] \Pr(\xv) - \Pr(\xv) \overbrace{ \class{yellow}{\int y \Pr(y|\xv) \diff y}}^{=~\Ebb [y|\xv]} )}_{=~0} \diff \xv = 0 \end{align*} $$

偏差方差分解

$$ \begin{align*} \Ebb_{(\xv,y)} [(f (\xv) - y)^2] & = \Ebb_{(\xv,y)} [(\overbrace{f (\xv) - \Ebb [y|\xv]}^{\mathrm{independent~of~}y})^2] + \overbrace{\Ebb_{(\xv,y)} [(\Ebb [y|\xv] - y)^2]}^{\mathrm{noise~of~}y} \\ & = \Ebb_{\xv} [(f (\xv) - \Ebb [y|\xv])^2] + \noise \end{align*} $$

第二项标记中的噪声是问题所固有的，与模型$f$的选择无关

根据第一项，使得泛化均方误差最小的$f^\star (\xv) = \Ebb [y|\xv]$

• 由于我们不知道$y$的分布，因此没法精确计算$\Ebb [y|\xv]$
• 如果数据足够多，也可以得到近乎准确的$\Ebb [y|\xv]$
• 但通常我们只有大小为$m$的数据集$D$
• 不同的$D$上训练得到不同的$f_D$，不同的$f_D$对$\xv$有不同的预测

将数据集$D$的随机性也考虑进来，注意$\noise$与$D$无关，故

$$ \begin{align*} E = \Ebb_D \Ebb_{(\xv,y)} [(f_D (\xv) & - y)^2] = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb [y|\xv])^2] + \noise \end{align*} $$

偏差方差分解

泛化均方误差$E = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb [y|\xv])^2] + \noise$

引入$\xv$的期望预测$\Ebb_D [f_D (\xv)]$，易知有分解

$$ \begin{align*} & (f_D (\xv) - \Ebb [y|\xv])^2 = (f_D (\xv) - \Ebb_D [f_D (\xv)] + \Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2 \\ & = (f_D (\xv) - \Ebb_D [f_D (\xv)])^2 + (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2 \\ & \qquad + 2 (f_D (\xv) - \Ebb_D [f_D (\xv)]) (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]) \end{align*} $$

注意$\Ebb_D [f_D (\xv)]$与$D$无关，对交叉项有

$$ \begin{align*} \Ebb_D & [(f_D (\xv) - \Ebb_D [f_D (\xv)]) (\overbrace{\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]}^{\mathrm{independent~of~}D})] \\ & = (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]) \underbrace{\Ebb_D [f_D (\xv) - \Ebb_D [f_D (\xv)]]}_{=~0} = 0 \end{align*} $$

偏差方差分解

$$ \begin{align*} E & = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2] + \Ebb_{\xv} \Ebb_D [(\overbrace{\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]}^{\mathrm{independent~of~}D})^2] + \noise \\ & = \underbrace{\Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2]}_{\variance} + \underbrace{\Ebb_{\xv} [(\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2]}_{\bias^2} + \noise \end{align*} $$

综上，泛化均方误差的偏差方差分解为

$$ \begin{align*} \Ebb_{(\xv,y)} \Ebb_D [(f_D (\xv) - y)^2] = \bias^2 + \variance + \noise \end{align*} $$

• 偏差$\bias^2 = \Ebb_{\xv} [(\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2]$，学习算法的拟合能力
• 方差$\variance = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2]$，对数据集扰动的敏感度
• 噪声$\noise = \Ebb_{(\xv,y)} [(\Ebb [y|\xv] - y)^2]$，问题固有，无法优化

偏差方差分解

偏差方差窘境

训练不足时，模型拟合能力不强，数据集扰动的影响不大

训练程度加深后，模型对数据集扰动很敏感，方差占主导